package pers.qianyu.month_202012.date_20201230;

/**
 * 329. 矩阵中的最长递增路径
 * https://leetcode-cn.com/problems/longest-increasing-path-in-a-matrix/
 *
 * @author mizzle rain
 * @date 2020-12-30 21:24
 */
public class LongestIncreasingPath {
    private int h, w;
    // 使用备忘录，记忆化搜索
    private int[][] memo;
    private int[][] directions = {{0, 1}, {1, 0}, {-1, 0}, {0, -1}};

    private int recur(int i, int j, int[][] matrix) {
        if (memo[i][j] != 0) {
            return memo[i][j];
        }
        int res = 1;
        for (int[] direction : directions) {
            int x = i + direction[0];
            int y = j + direction[1];
            if (x >= 0 && y >= 0 && x < h && y < w && matrix[x][y] > matrix[i][j]) {
                res = Math.max(res, recur(x, y, matrix) + 1);
            }
        }
        memo[i][j] = res;
        return res;
    }

    public int longestIncreasingPath(int[][] matrix) {
        h = matrix.length;
        if (h == 0) {
            return 0;
        }
        w = matrix[0].length;
        memo = new int[h][w];
        int max = 0;
        for (int i = 0; i < h; i++) {
            for (int j = 0; j < w; j++) {
                max = Math.max(max, recur(i, j, matrix));
            }
        }
        return max;
    }
}
